package commons.lang;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

import commons.utils.StringUtils;

/**
 * This class represents a rooted tree. Each node, "Atom," contains information
 * about the data it holds and the information regarding its position within the
 * tree.
 * <p>
 * A rooted tree is a special kind of tree that allows an arbitrary number of
 * children. Each node in the tree has two pointers. A pointer to the left most
 * child, and a pointer to the right sibling. There is also a pointer to the
 * parent(root).
 * <p>
 * 1. Left = points to the leftmost child of node x.<br>
 * 2. Right = points to the sibling of x immediately to the right. <br>
 * 3. Root = points to the parent of x.
 * <p>
 * A rooted tree uses a O(n) space for any n-node tree. The order of the tree is
 * based on the position the data is inserted. There is no default position for
 * inserting the node. Specific funtions exist to insert the node in a desired
 * position.
 * 
 * @author Vadim Pertsovskiy
 * @version 1.0
 */
public class Atom implements java.io.Serializable {
    private static final long serialVersionUID = 1L;
    private final int DEBUG_LEVEL = 0;
    private Atom _root;
    private Atom _parent;
    private Atom _left;
    private Atom _right;
    private Object _name;
    private Object _value;
    private Object _attribute;
    private List<?> _attribList;
    private HashMap<Object, Object> _attrib = new HashMap<Object, Object>();
    private boolean _cdataWrap;

    /**
     * Creates an empty node(atom)
     */
    public Atom() {
    }

    /**
     * Creates a node with a name and a value.
     * 
     * @param n
     *            name of the node.
     * @param v
     *            value of the node.
     */
    public Atom(Object n, Object v) {
	_name = n;
	_value = v;
    }

    public Atom(Object n, Object v, boolean cdataWrap) {
	_name = n;
	_value = v;
	_cdataWrap = cdataWrap;
    }

    public void dispose() {
	_root = null;
	_left = null;
	_right = null;
	_name = null;
	_value = null;
	_attrib = null;
	_attribute = null;
    }

    /**
     * Creates a node with a name, a value and a parent.
     * 
     * @param r
     *            parent of the node.
     * @param n
     *            name of the node.
     * @param v
     *            value of the node.
     */
    public Atom(Atom r, Object n, Object v) {
	_root = r;
	_name = n;
	_value = v;
    }

    public Atom getRoot() {
	return _root;
    }

    public Atom getLeft() {
	return _left;
    }

    public Atom getRight() {
	return _right;
    }

    public Object getName() {
	return _name;
    }

    public Object getValue() {
	return _value;
    }

    public Object getAttribute() {
	return _attribute;
    }

    public List<?> getAttribList() {
	return _attribList;
    }

    public final HashMap<Object, Object> getAttrib() {
	return _attrib;
    }

    /**
     * Sets the parent of the current node.
     * 
     * @param r
     *            parent of the node.
     */
    public void setRoot(Atom r) {
	_root = r;
    }

    /**
     * Sets a pointer to the left most child of this node.
     * 
     * @param l
     *            the left most child node.
     */
    public void setLeft(Atom l) {
	_left = l;
    }

    /**
     * Sets a pointer to the right sibling of this node.
     * 
     * @param r
     *            right sibling of this node.
     */
    public void setRight(Atom r) {
	_right = r;
    }

    /**
     * Sets the name of this node.
     * 
     * @param o
     *            the name of this node.
     */
    public void setName(Object o) {
	_name = o;
    }

    /**
     * Appends the data to the current value of the node.
     * 
     * @param o
     *            data to append.
     */
    public void setValue(Object o) {
	if (_value != null) {
	    StringBuffer sb = new StringBuffer((String) _value);
	    sb.append(o);
	    _value = sb.toString();
	} else {
	    _value = o;
	}
    }

    public void setAttribute(Object o) {
	_attribute = o;
    }

    public void setAttribList(List<?> lst) {
	_attribList = lst;
    }

    public void setAttrib(Object key, Object value) {
	_attrib.put(key, value);
    }

    /**
     * Replaces the current value of the node.
     * 
     * @param o
     *            new value of the node
     * @see #setValue
     */
    public void replaceValue(Object o) {
	_value = o;
    }

    public void deleteChild(Object name) {
	Atom temp = _left;
	Atom parent = _root;
	while (temp != null && !temp._name.equals(name)) {
	    parent = temp;
	    temp = temp._right;
	}
	if (parent.equals(_root)) {
	    setLeft(temp._right);
	} else {
	    parent._right = temp._right;
	}
    }

    public void deleteAtom(Object name) {
	Atom a = find(name);
	if (a != null) {
	    if (a.equals(a._parent._left)) {
		a._parent._left = null;
	    } else if (a.equals(a._parent._right)) {
		a._parent._right = a._right;
	    }
	}
    }

    /**
     * Inserts a node as a child of the current node. If the left pointer is not
     * empty, the child is inserted as the right most sibling of the left node.
     * 
     * @param a
     *            the child node to insert.
     */
    public void insertChild(Atom a) {
	if (_left == null) {
	    _left = a;
	    a._root = this;
	    a._parent = this;
	} else {
	    Atom temp = _left;
	    while (temp._right != null) {
		temp = temp._right;
	    }
	    temp._right = a;
	    a._root = temp._root;
	    a._parent = temp;
	}
    }

    public void insertChildSorted(Atom a) {
	if (_left == null) {
	    _left = a;
	    a._root = this;
	    a._parent = this;
	} else {
	    boolean comparable = a._value instanceof Comparable;
	    Atom temp = _left;
	    boolean loop = false;
	    while (temp._right != null && (comparable && ((Comparable) temp._right._value).compareTo(a._value) <= 0)) {
		temp = temp._right;
		if (!loop) {
		    loop = true;
		}
	    }
	    if (temp._right == null) {
		if (loop) {
		    temp._right = a;
		    a._parent = temp;
		} else {
		    if (comparable && ((Comparable) temp._value).compareTo(a._value) > 0) {
			a._right = temp;
			temp._root._left = a;
			a._parent = temp._root;
		    } else {
			temp._right = a;
			a._parent = temp;
		    }
		}
	    } else {
		Atom tempRight = temp._right;
		a._right = tempRight;
		temp._right = a;
		a._parent = temp;
	    }
	    a._root = temp._root;
	}
    }

    /**
     * Inserts a node as a child of the current node. If the left pointer is not
     * empty, the child is inserted as the right most sibling of the left node.
     * 
     * @param n
     *            the name of the child node.
     * @param v
     *            the value of the child node.
     */
    public void insertChild(Object n, Object v) {
	Atom a = new Atom(n, v);
	insertChild(a);
    }

    /**
     * Inserts a node as a child of the current node. If the left pointer is not
     * empty, the child is inserted as the right most sibling of the left node.
     * 
     * @param n
     *            the name of the child node.
     * @param v
     *            the value of the child node.
     * @param cdataWrap
     *            if true - wrap the value in CDATA, do not encode it.
     */
    public void insertChild(Object n, Object v, boolean cdataWrap) {
	Atom a = new Atom(n, v, cdataWrap);
	insertChild(a);
    }

    /**
     * Inserts a node as a child of the current node. If the left pointer is not
     * empty, the child is inserted as the right most sibling of the left node.
     * 
     * @param n
     *            the name of the child node.
     * @param v
     *            the value of the child node.
     * @return the newly created child node.
     */
    public Atom insertChildReturn(Object n, Object v) {
	Atom a = new Atom(n, v);
	insertChild(a);
	return a;
    }

    /**
     * Inserts a node as the right most sibling of this node.
     * 
     * @param a
     *            the node to insert as the sibling.
     */
    public void insertEqual(Atom a) {
	if (_right == null) {
	    _right = a;
	    a._root = _root;
	    a._parent = this;
	} else {
	    Atom temp = _right;
	    while (temp._right != null) {
		temp = temp._right;
	    }
	    temp._right = a;
	    a._root = temp._root;
	    a._parent = temp;
	}
    }

    /**
     * Inserts a node as the right most sibling of this node.
     * 
     * @param n
     *            the name of the sibling node.
     * @param v
     *            the value of the sibling node.
     */
    public void insertEqual(Object n, Object v) {
	Atom a = new Atom(n, v);
	insertEqual(a);
    }

    /**
     * Prints the current tree recursively. The children are printed first,
     * followed by the siblings.
     */
    public void printTree() {
	if (_root == null) {
	    System.out.println((String) _name + " - " + _value + " - root: null\n");
	} else {
	    System.out.println((String) _name + " - " + _value + " - root: " + _root._name + "\n");
	}
	if (_left != null) {
	    System.out.print("LEFT: ");
	    _left.printTree();
	}
	if (_right != null) {
	    System.out.print("RIGHT: ");
	    _right.printTree();
	}
    }

    /**
     * Searches for a node recursively that matches the name.
     * <p>
     * In the worst case scenario, the find will take O(n)<br>
     * There is no easy way to speed it up, considering that the tree is not
     * sorted.
     * 
     * @param n
     *            the name of the lost node.
     * @return the found node, or null if not found.
     */
    public Atom find(Object n) {
	Atom returnAtom = null;
	if (_name.equals(n)) {
	    return this;
	}
	if (_left != null) {
	    returnAtom = _left.find(n);
	}
	if (returnAtom == null) {
	    if (_right != null) {
		returnAtom = _right.find(n);
	    }
	}
	return returnAtom;
    }

    /**
     * Searches recursively for all nodes that match the name.
     * 
     * @param n
     *            the name of the lost node
     * @return all the nodes that match the name
     */
    public List<Atom> findAll(Object n) {
	List<Atom> list = new ArrayList<Atom>(10);
	findAllAux(n, list);
	return list;
    }

    /**
     * Helper class for findAll
     */
    private void findAllAux(Object n, List<Atom> list) {
	if (_name.equals(n))
	    list.add(this);
	if (_left != null)
	    _left.findAllAux(n, list);
	if (_right != null)
	    _right.findAllAux(n, list);
    }

    /**
     * @return the next, right, sibling of this node.
     * @see #getRight
     */
    public Atom getNextEqual() {
	return _right;
    }

    /**
     * Searches iteratively for a sibling node that matches the name.
     * 
     * @param ob
     *            the name of the lost node.
     * @return a sibling that matches the name.
     * @see #find
     */
    public Atom findEqual(Object ob) {
	if (_name.equals(ob)) {
	    return this;
	}
	Atom temp = new Atom();
	temp = _right;
	while (temp != null) {
	    if (temp._name.equals(ob)) {
		return temp;
	    }
	    temp = temp._right;
	}
	return null;
    }

    /**
     * Searches iteratively for all the siblings that match the name.
     * 
     * @param ob
     *            the name of the lost node(s).
     * @return a vector of nodes that matched the name.
     */
    public List<Atom> findAllEqual(Object ob) {
	List<Atom> vr = new ArrayList<Atom>();
	if (_name.equals(ob)) {
	    vr.add(this);
	}
	Atom temp;
	temp = _right;
	while (temp != null) {
	    if (temp._name.equals(ob)) {
		vr.add(temp);
	    }
	    temp = temp._right;
	}
	return vr;
    }

    /**
     * Searches iteratively for a sibling node that matches the name. If the
     * node matches the name, its left child is added to the vector instead of
     * itself.
     * 
     * @param ob
     *            the name of the lost node(s).
     * @return a vector of left most children whose parents match the name.
     * @see #findAllEqual
     */
    public List<Atom> findAllEqualNext(Object ob) {
	List<Atom> vr = new ArrayList<Atom>();
	if (_name.equals(ob)) {
	    if (_left != null) {
		vr.add(_left);
	    }
	}
	Atom temp;
	temp = _right;
	while (temp != null) {
	    if (temp._name.equals(ob)) {
		if (temp._left != null) {
		    vr.add(temp._left);
		}
	    }
	    temp = temp._right;
	}
	return vr;
    }

    /**
     * Searches iteratively for a child node that matches the name.
     * 
     * @param name
     *            the name of the lost child node.
     * @return a child node that matches the name or null if the node was not
     *         found.
     * @see #find
     */
    public Atom findChild(Object name) {
	Atom temp = _left;
	while (temp != null) {
	    if (temp._name.equals(name)) {
		return temp;
	    }
	    temp = temp._right;
	}
	return null;
    }

    /**
     * Returns a name, value pair for all the children of this node.
     * 
     * @return a hashtable of all the children.
     */
    public Map<Object, Object> getChildren() {
	// one level
	Map<Object, Object> hm = new LinkedHashMap<Object, Object>();
	Atom temp = _left;
	while (temp != null) {
	    hm.put(temp._name, temp._value);
	    temp = temp._right;
	}
	return hm;
    }

    /**
     * Returns a name, value pair for all the children, and subchildren of this
     * node.
     * 
     * @return a hashtable of all the children and their children ...
     */
    public Map<String, ? extends Object> getAllChildren() {
	// all levels
	Map<String, Object> hm = new LinkedHashMap<String, Object>();
	if (_left != null) {
	    _left.getAllChildrenSub(hm, "");
	}
	return hm;
    }

    private void getAllChildrenSub(Map<String, Object> hm, String prefix) {
	StringBuffer sb = new StringBuffer(prefix);
	if (!("".equals(prefix))) {
	    sb.append(".");
	}
	sb.append(_name);
	hm.put(sb.toString(), _value);
	if (_left != null) {
	    _left.getAllChildrenSub(hm, sb.toString());
	}
	if (_right != null) {
	    _right.getAllChildrenSub(hm, prefix);
	}
    }

    /**
     * @return true if there is a left child, false otherwise.
     */
    public boolean hasLeft() {
	return _left != null;
    }

    /**
     * @return true if there is a right child, false otherwise.
     */
    public boolean hasRight() {
	return _right != null;
    }

    /**
     * @return the current node as a string. Ex: Atom -- name=nm value=vl
     */
    @Override
    public String toString() {
	return "Atom -- name=" + _name + " value=" + _value + " attrib=" + _attrib;
    }

    /**
     * Returns the current branch as a valid xml string.
     */
    public String toXMLString() {
	StringBuffer sb = new StringBuffer();
	toXMLString(sb, "");
	return sb.toString();
    }

    public void toXMLString(StringBuffer sb, String offset) {
	if (_attribute != null) {
	    sb.append(offset).append("<").append(_name).append(" ").append(_attribute).append(">");
	} else {
	    sb.append(offset).append("<").append(_name).append(">");
	}
	String value = _value != null ? _value.toString().trim() : "";
	String trm = _cdataWrap ? "<![CDATA[" + value + "]]>" : StringUtils.formatXMLvalues(value);
	if (_left != null) {
	    sb.append("\n");
	    _left.toXMLString(sb, offset + "  ");
	    if (!(trm.equals(""))) {
		sb.append(offset).append("  ").append(trm).append("\n");
	    }
	    sb.append(offset).append("</").append(_name).append(">\n");
	} else {
	    sb.append(trm).append("</").append(_name).append(">\n");
	}
	if (_right != null) {
	    _right.toXMLString(sb, offset);
	}
    }

    /**
     * Method for debug print statements
     */
    protected void printDebug(String debugString) {
	printDebug(debugString, 1);
    }

    /**
     * Method for debug print statements
     */
    protected void printDebug(String debugString, int debugLevel) {
	if (debugLevel <= DEBUG_LEVEL) {
	    System.out.println(debugString);
	}
    }
}
